package domain.simplex;

import utils.exception.SimplexException;
import utils.exception.SimplexInfeasibleException;

/**
 * @see Intro to Algorithms, 2nd edition, p812
 * @author j55wu
 * 
 */
public class SimplexInitializer {
	SimplexSlackForm sf;

	public SimplexInitializer(SimplexSlackForm sf) {
		this.sf = sf;
	}

	// must return a new copy!
	public SimplexSlackForm initialize() throws SimplexException,
			SimplexInfeasibleException {
		// get the min Bi
		int l = minBi(sf.getBi());
		if (sf.getBi(l) >= 0) {
			// this is a feasible solution, just return
			sf.setV(0);
		} else {
			// System.err.println("Not handled yet.");
			sf = initializeNewSlackForm(sf, l, sf.getCj());
		}
		return sf;
	}

	// l is the min index that has B_l < 0
	private SimplexSlackForm initializeNewSlackForm(SimplexSlackForm mysf,
			int l, double[] myCj) throws SimplexException,
			SimplexInfeasibleException {
		double[] originalCj = new double[myCj.length];
		System.arraycopy(myCj, 0, originalCj, 0, myCj.length);
		// add -x0 to LHS for each basic var
		for (Integer i : mysf.getBasicVars()) {
			mysf.setAij(i, 0, -1);
		}
		// set objective function z = -x0
		for (int i = 1; i < mysf.getCj().length; i++) {
			mysf.setCj(i, 0);
		}
		mysf.setCj(0, -1);
		// Add x0 as nonbasic var; Note: Bi, v remains unchanged
		mysf.addAsNonBasicVar(0);
		// pivot once
		Simplex.pivoting(mysf, l, 0);
		// now we have a feasible solution. while loop in simplex until the
		// optimal is found
		int e = Simplex.findPosNBVar(mysf);
		while (e >= 0) {
			int result = Simplex.theWhileLoop(mysf, e);
			if (result < 0) {
				throw new SimplexException("Unbounded. Quit.");
			}
			e = Simplex.findPosNBVar(mysf);
		}
		// if the basic solution set x0 to 0, i.e., if x0 is in nonbasic or is
		// in basic but has value 0
		boolean feasible = false;
		if (mysf.getNonbasicVars().contains(new Integer(0))) {
			feasible = true;
		} else {
			for (int i = 0; i < mysf.getBasicVars().size(); i++) {
				int var = mysf.getBasicVars().get(i);
				if (var == 0 && mysf.getBi(var) == 0) {
					feasible = true;
				}
			}
		}
		if (feasible) {
			// restore
			mysf = this.finalSlackForm(mysf, originalCj);
		} else {
			throw new SimplexInfeasibleException("Infeasible.");
		}
		return mysf;
	}

	private SimplexSlackForm finalSlackForm(SimplexSlackForm mysf,
			double[] originalCj) {
		// case 1: if x_0 is a basic var
		if (mysf.getBasicVars().contains(new Integer(0))) {
			mysf.clearAijRow(0);
			mysf.rmBasicVar(0);
		} else {
			// case2: x_0 is a nonbasic var
			mysf.clearAijColumn(0);
			mysf.rmNonBasicVar(0);
		}
		// Aij, NB, B already modified as above
		// Bi not affected
		// V changed as follows
		// now change Cj, i.e, restore the objective function, make sure only
		// nonbasic vars reside in Z
		for (int i = 0; i < originalCj.length; i++) {
			if (originalCj[i] == 0) {
				// mysf.setCj(i, 0);
				continue;
			}
			// i stands for x_i in objective func
			if (mysf.getBasicVars().contains(new Integer(i))) {
				// a basic var? need to be replaced by non-basic vars
				double coef = originalCj[i];
				// update v first
				double newv = coef * mysf.getBi(i);
				mysf.setV(newv);
				// update other nonbasic vars in objective func, i.e., replace
				// x_i in objective func
				for (int j = 0; j < mysf.getAijRow(i).length; j++) {
					if (i == j) {
						// x_i is removed from Cj
						mysf.setCj(j, 0);
						continue;
					}
					double val = (-1) * coef * mysf.getAij(i, j)
							+ originalCj[j];
					mysf.setCj(j, val);
				}
			} else {
				// a nonbasic var, copy this to mysf
				mysf.setCj(i, originalCj[i]);
			}
		}
		return mysf;
	}

	private int minBi(double[] bi) {
		int ret = 0;
		for (int i = 0; i < bi.length; i++) {
			if (bi[i] < bi[ret]) {
				ret = i;
			}
		}
		return ret;
	}
}
